The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(1(0(x1))) → 0(2(3(1(3(0(x1))))))
0(2(1(x1))) → 3(1(3(0(2(x1)))))
0(2(1(x1))) → 0(2(3(3(1(3(x1))))))
0(2(1(x1))) → 0(4(3(1(3(2(2(x1)))))))
0(2(1(x1))) → 0(2(3(2(2(1(3(2(x1))))))))
1(0(0(x1))) → 2(3(1(3(0(0(x1))))))
0(0(2(0(x1)))) → 0(0(4(4(3(2(0(x1)))))))
0(1(2(1(x1)))) → 0(3(1(3(1(3(2(x1)))))))
0(1(3(5(x1)))) → 0(5(4(4(3(1(4(x1)))))))
0(1(3(5(x1)))) → 3(5(4(3(1(3(2(0(x1))))))))
0(1(5(1(x1)))) → 5(3(1(3(0(1(x1))))))
0(2(1(4(x1)))) → 0(3(2(2(1(4(x1))))))
0(2(1(4(x1)))) → 3(2(1(0(4(3(x1))))))
0(2(2(1(x1)))) → 3(2(0(2(3(1(x1))))))
0(2(2(5(x1)))) → 3(1(3(2(2(0(4(5(x1))))))))
0(2(4(4(x1)))) → 3(2(0(4(4(5(4(x1)))))))
0(2(4(5(x1)))) → 3(2(0(4(5(x1)))))
0(3(3(4(x1)))) → 5(4(3(2(3(0(x1))))))
0(3(5(1(x1)))) → 5(4(3(2(2(0(1(x1)))))))
1(0(2(4(x1)))) → 2(3(0(3(1(4(x1))))))
1(1(2(5(x1)))) → 1(3(2(2(1(5(x1))))))
0(0(0(3(4(x1))))) → 0(0(4(4(5(2(3(0(x1))))))))
0(0(1(1(5(x1))))) → 5(0(3(1(3(1(0(5(x1))))))))
0(1(2(2(4(x1))))) → 4(3(2(1(2(3(0(x1)))))))
0(1(5(1(4(x1))))) → 5(3(1(0(4(3(1(x1)))))))
0(2(2(0(1(x1))))) → 0(4(3(0(2(3(2(1(x1))))))))
0(2(2(2(5(x1))))) → 3(2(2(5(4(3(2(0(x1))))))))
0(2(2(5(0(x1))))) → 3(2(2(0(5(2(3(0(x1))))))))
0(3(4(1(4(x1))))) → 2(3(3(1(0(5(4(4(x1))))))))
0(4(1(3(4(x1))))) → 3(1(3(0(4(4(5(x1)))))))
0(4(2(2(4(x1))))) → 3(2(2(0(4(4(x1))))))
0(4(2(4(1(x1))))) → 3(1(0(4(4(3(2(x1)))))))
0(5(2(1(5(x1))))) → 5(4(5(2(3(1(0(x1)))))))
1(0(2(2(4(x1))))) → 2(2(0(4(3(1(4(x1)))))))
1(0(2(2(4(x1))))) → 2(3(3(2(1(0(4(3(x1))))))))
1(2(2(0(1(x1))))) → 4(3(2(1(0(2(3(1(x1))))))))
1(2(3(5(0(x1))))) → 5(2(3(1(3(0(x1))))))
1(2(4(3(5(x1))))) → 5(4(3(1(3(2(x1))))))
0(0(1(3(3(5(x1)))))) → 0(3(2(3(0(1(5(x1)))))))
0(0(2(2(3(0(x1)))))) → 0(2(3(0(3(2(0(x1)))))))
0(0(2(2(5(1(x1)))))) → 0(3(0(2(3(2(1(5(x1))))))))
0(0(3(5(3(0(x1)))))) → 0(5(0(3(1(3(3(0(x1))))))))
0(0(4(0(5(1(x1)))))) → 0(0(4(0(4(3(1(5(x1))))))))
0(0(4(1(3(0(x1)))))) → 0(0(3(2(3(0(1(4(x1))))))))
0(1(0(3(4(5(x1)))))) → 3(1(0(4(3(5(0(4(x1))))))))
0(1(4(0(2(5(x1)))))) → 0(5(2(0(4(4(1(x1)))))))
0(1(5(3(4(0(x1)))))) → 0(4(4(2(0(3(1(5(x1))))))))
0(2(1(5(3(5(x1)))))) → 3(2(1(3(5(1(5(0(x1))))))))
0(3(5(2(4(1(x1)))))) → 0(0(5(4(3(2(1(x1)))))))
0(5(0(1(5(4(x1)))))) → 3(1(3(0(0(5(4(5(x1))))))))
0(5(1(1(3(4(x1)))))) → 4(1(0(4(5(4(3(1(x1))))))))
0(5(3(4(1(4(x1)))))) → 5(4(0(4(3(1(3(x1)))))))
0(5(3(4(1(5(x1)))))) → 0(3(2(1(0(5(4(5(x1))))))))
0(5(5(0(1(5(x1)))))) → 0(5(5(3(2(1(5(0(x1))))))))
1(0(2(4(0(5(x1)))))) → 1(4(0(3(2(3(0(5(x1))))))))
1(1(4(0(1(0(x1)))))) → 0(3(1(3(1(4(1(0(x1))))))))
1(2(1(0(2(1(x1)))))) → 1(1(3(2(0(2(1(x1)))))))
1(2(4(0(3(4(x1)))))) → 3(2(0(4(3(3(1(4(x1))))))))
1(2(4(3(3(0(x1)))))) → 4(0(2(3(3(1(3(0(x1))))))))
1(2(4(3(3(5(x1)))))) → 3(2(3(2(5(4(3(1(x1))))))))
1(2(4(3(4(5(x1)))))) → 3(1(3(2(4(5(4(x1)))))))
1(2(4(5(1(0(x1)))))) → 0(4(2(1(3(1(5(x1)))))))
1(2(4(5(3(4(x1)))))) → 4(3(2(2(1(3(5(4(x1))))))))
1(2(5(5(3(0(x1)))))) → 5(2(3(3(1(3(5(0(x1))))))))
0(0(2(4(5(3(5(x1))))))) → 2(0(5(4(3(5(3(0(x1))))))))
0(1(0(5(3(5(1(x1))))))) → 1(0(0(5(5(3(1(3(x1))))))))
0(1(2(2(5(2(0(x1))))))) → 5(1(0(3(2(2(2(0(x1))))))))
0(2(1(5(4(0(1(x1))))))) → 0(0(5(1(2(3(1(4(x1))))))))
0(2(3(4(1(1(4(x1))))))) → 3(1(0(4(4(1(2(0(x1))))))))
0(2(4(1(1(5(1(x1))))))) → 3(1(0(5(4(1(1(2(x1))))))))
0(2(5(0(4(0(1(x1))))))) → 0(5(1(0(4(3(2(0(x1))))))))
0(2(5(5(3(5(1(x1))))))) → 0(5(5(1(5(5(3(2(x1))))))))
0(4(0(3(5(2(0(x1))))))) → 0(4(0(4(5(3(2(0(x1))))))))
0(4(1(1(4(1(5(x1))))))) → 0(4(3(1(4(1(1(5(x1))))))))
0(4(1(4(0(3(5(x1))))))) → 3(1(5(0(0(4(3(4(x1))))))))
0(5(1(3(4(2(4(x1))))))) → 5(4(4(0(3(1(5(2(x1))))))))
1(0(3(3(3(4(0(x1))))))) → 0(3(0(3(3(1(4(5(x1))))))))
1(0(3(4(4(3(5(x1))))))) → 5(4(3(1(3(0(2(4(x1))))))))
1(2(0(4(1(3(5(x1))))))) → 5(4(2(3(1(4(1(0(x1))))))))
1(2(4(0(5(3(5(x1))))))) → 5(1(3(2(3(5(0(4(x1))))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1.
The certificate found is represented by the following graph.

Start state: 6745
Accept states: [6746, 6747]
Transitions:
6745→6746[0_1|0]
6745→6747[1_1|0]
6745→6745[2_1|0, 3_1|0, 4_1|0, 5_1|0]
6745→6748[2_1|1]
6745→6753[1_1|1]
6745→6760[5_1|1]
6745→6767[0_1|1]
6745→6774[5_1|1]
6745→6778[4_1|1]
6745→6784[4_1|1]
6745→6790[0_1|1]
6745→6795[4_1|1]
6745→6802[4_1|1]
6748→6749[3_1|1]
6749→6750[1_1|1]
6750→6751[3_1|1]
6751→6752[4_1|1]
6752→6747[5_1|1]
6752→6753[5_1|1]
6753→6754[3_1|1]
6754→6755[4_1|1]
6755→6756[5_1|1]
6756→6757[2_1|1]
6757→6758[3_1|1]
6758→6759[2_1|1]
6759→6747[3_1|1]
6759→6753[3_1|1]
6760→6761[4_1|1]
6761→6762[0_1|1]
6762→6763[2_1|1]
6763→6764[2_1|1]
6764→6765[3_1|1]
6765→6766[1_1|1]
6766→6746[3_1|1]
6766→6767[3_1|1]
6766→6790[3_1|1]
6767→6768[2_1|1]
6768→6769[3_1|1]
6769→6770[4_1|1]
6770→6771[5_1|1]
6771→6772[2_1|1]
6772→6773[2_1|1]
6773→6746[3_1|1]
6773→6767[3_1|1]
6773→6790[3_1|1]
6774→6775[4_1|1]
6775→6776[0_1|1]
6776→6777[2_1|1]
6777→6746[3_1|1]
6777→6767[3_1|1]
6777→6790[3_1|1]
6778→6779[5_1|1]
6779→6780[4_1|1]
6780→6781[2_1|1]
6781→6782[3_1|1]
6782→6783[1_1|1]
6783→6747[3_1|1]
6783→6753[3_1|1]
6784→6785[5_1|1]
6785→6786[4_1|1]
6786→6787[4_1|1]
6787→6788[0_1|1]
6788→6789[2_1|1]
6789→6746[3_1|1]
6789→6767[3_1|1]
6789→6790[3_1|1]
6790→6791[3_1|1]
6791→6792[2_1|1]
6792→6793[3_1|1]
6793→6794[4_1|1]
6794→6746[5_1|1]
6794→6767[5_1|1]
6794→6790[5_1|1]
6795→6796[5_1|1]
6796→6797[3_1|1]
6797→6798[1_1|1]
6798→6799[2_1|1]
6799→6800[2_1|1]
6800→6801[3_1|1]
6801→6747[4_1|1]
6801→6753[4_1|1]
6802→6803[4_1|1]
6803→6804[0_1|1]
6804→6805[2_1|1]
6805→6806[2_1|1]
6806→6746[3_1|1]
6806→6767[3_1|1]
6806→6790[3_1|1]

(2) BOUNDS(O(1), O(n^1))